Otus.png

Heading.png

ВКЛЮЧИТЬ ЗАПИСЬ!!!

Заполните опросник перед началом занятия: https://docs.google.com/forms/d/e/1FAIpQLSdyc0BGGcf1p2KXmU__kQnaLPMVPcBB1wcHSmZuOo4vKcdbCA/viewform

Eniac.jpg

ENIAC 1943, University of Pennsylvanya

  • Первый в мире цифровой компьютер общего назначения;
  • Имел 20 слов внутренней памяти (аккумуляторы), каждый содержал 10 цифр со знаком;
  • Выполнял 5000 сложений/вычитаний между аккумуляторами, 385 умножений, 40 делений и 3 операции извлечения квадратного корня в секунду;
  • Имел 100 слов внешней памяти на магнитных барабанах;
  • Программировался переключением проводов и набором на телефонных дисках, так как языки программирования еще не существовали;
  • Перепрограммирование занимало 3 недели.

Фон-Ноймановская модель архитектуры компьютеров

Упорядочила архитектуру компьютеров FonNeumann.png

  • CPU - производит операции с регистрами и памятью (DataPath - производит операции над данными - "мышцы" машины, Finite State Machine - конечная машина состояний - "мозг" машины);
  • Read/Write memory - содержит W слов, каждое из которых имеет N бит. Главная память. Работает как массив. Когда нужно обратиться к памяти, CPU посылает памяти индекс массива, который мы называем адрес, и память через какое-то время возвращает N-битное значение, которое хранится в этом адресе. Запись в память происходит аналогично, только в обратном направлении.
  • Устройства ввода-вывода - для коммуникации с внешним миром - накопителями на жестких дисках, периферией.

Перечислите ВСЕ виды памяти, которые вы знаете

Memory.png

Как сделать такое же большое хранилище, как HDD и такое же быстрое, как SRAM?

Общая иерархия памяти (всё является кешом для чего-то другого)

Hierarchy.png Да, флеш-память иногда является кешом для HDD

Будем говорить о Read/Write memory в Фон-Ноймановском понимании этого слова

Виртуальная память

Есть два типа адресов:

  • физические
  • виртуальные

Перевод из физических адресов в виртуальные производится аппаратно в помощью таблицы (page map), поддерживаемой операционной системой. VirtualMemory.png

  • абстрагирует адреса, разделяя адреса, используемые конкретным процессом от физических адресов;
  • обеспечивает раздельное исполнение процессов;
  • увеличивает размер адресного пространства за пределы доступной физической памяти, используя своп на другой носитель. Качество менеджера виртуальной памяти может оказывать значительный эффект на производительность всей системы. А где на этой схеме кэши L1, L2, L3? Вопрос к аудитории: где они должны находиться? Между процессором и памятью? Да, но где? До MMU или за MMU? Работают они с виртуальными адресами или с физическими?

Контексты

Каждый программа работает в своем контексте. Page map дает контексту информацию, где находится тот или иной виртуальный адрес - в основной памяти или на диске и где конкретно. Context.png При переключении контекстов нужно перезагружать page map? Да. Потому что page map один, а контекстов много.

Кэши

Как они работают?

  • процессор выставляет адрес, который он хочет прочитать/записать в кэш;
  • два варианта:
    • cache hit - адрес есть в кэше, возвращаются соответствующие данные;
    • cache miss - адеса нет в кэше, делаем запрос в основную память, возвращаем результат процессору; кроме того, обновляем кэш (возможно, вытесняя какие-то другие данные);
  • процессор должен понимать, что время выполнения его запроса может варьировааться.

Куда поместить кэш-память? До MMU или за MMU?

До MMU - кешируем виртуальные адреса, за MMU - кешируем физические адреса.

CachesVariants.png

Ваши варианты?

До MMU:

Плюсы:

  • отвечаем быстрее, потому что время MMU не учитывается;

Минусы:

  • надо сбрасывать кэш при переключении контекста, потому что кешируем виртуальные адреса;

За MMU:

Плюсы:

  • не надо сбрасывать кэш при переключении контекста, избегаем неактуальных данных;

Минусы:

  • медленнее, потому что есть время MMU.

Кэши: оптимальный вариант, берем лучшее из двух подходов

Caches.png Каждый виртуальный адрес (оффсет страницы) делится на 3 части:

  • собственно номер виртуальной страницы;
  • индекс массива в кэше;
  • индекс в кэш-линии.

Не ждём окончания работы MMU, сразу начинаем запрашивать данные из кеша. Кэш индексируется виртуальными адресами, а тэгируется физическими. В то время, как MMU использует номер виртуальной страницы, чтобы получить номер физической страницы, кэш использует индексную часть, чтобы найти в кэше адрес. Идет параллельный lookup из кэша и трансляция виртуального адреса в физический через MMU. Затем сравнивается физический адрес от MMU физический тэг от кэша. Если они совпадают, был cache hit. Если нет, то cache miss. Тогда возвращается результат из памяти и записывается в кэш.

Достоинства:

  • работает быстро, потому что lookup из кэша идет сразу же, и его не надо сбрасывать при переключении контекстов.

Недостаток:

  • чтобы увеличить размер кэша, надо увеличивать к-во бит в в виртуальном адресе.

Что такое memory management (управление памятью)?

MemoryManagement.png

Вопрос: что происходит, когда указатели на Stack и Heap встречаются?

Аллокация виртуальной памяти из приложения на уровне операционной системы

  • выдели мне кусок памяти по такому-то адресу такого-то размера
  • освободи мне кусок памяти по такому-то адресу такого-то размера
In [1]:
// Windows
// Возвращает зааллокированный указатель
// VirtualAlloc/VirtualFree
LPVOID VirtualAlloc
(  
    LPVOID lpAddress,       // базовый адрес, если NULL, то система сама выбирает адрес
                            // При этом адрес округляется до ближайшей границы блока размером 64 Кбайт.
    SIZE_T dwSize,          // размер
    DWORD flAllocationType, // тип аллокации (MEM_COMMIT, MEM_RESERVE, MEM_RESET, ...)
    DWORD flProtect         // защита (PAGE_NOACCESS, PAGE_GUARD, ...)
);

BOOL VirtualFree
(  
    LPVOID lpAddress,       // адрес
    SIZE_T dwSize,          // размер памяти
    DWORD dwFreeType        // тип операции (MEM_DECOMMIT, MEM_RELEASE, ...)
);

// Linux/MacOS
// mmap() / munmap()
// Создает / уничтожает новый маппинг виртуального адресного пространства процесса для использования в приложении
// Если addr == NULL, система сама выбирает адрес, иначе использует заданный адрес как хинт для выделения памяти 
// (округляя его до page size)
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);
// Перекрывающиеся маппинги недопустимы и система выбирает следующий свободный вариант, если маппинги перекрываются

Особенности выделения виртуальной памяти на разных платформах

Особенность Windows Linux
Резервирование/коммит Виртуальная память может быть либо только зарезервирована, либо закоммичена, то есть замаплена (либо в RAM, либо в swap). Маппинг может быть "раскоммичен". Маппинг всегда "коммитится", необходимости в этом нет
Сплит-джойн Каждый маппинг - это отдельная аллокация, поддерживаемая на уровне OS. Число вызовов VirtualFree() должно соответствовать числу вызовов VirtualAlloc() и туда должен подаваться тот же указатель - нет частичных особождений. Маппинги можно мержить и сплитить, число вызовов mmap не всегда соответствует числу вызовов munmap
Выравнивание Маппинг всегда начинается с адреса, выровненного по границе 64KB (более точно можно получить allocation granularity через GetSystemInfo). Запрос размера, меньшего, чем 64KB, неоптимален и приводит к неэффективному использованию и фрагментации адресного пространства. Маппинги могут начинаться с любого адреса, выровненного по размеру страницы (4KB). Можно мапить несколько страниц подряд и все эти маппинги склеятся между собой в один.
Количество маппингов Нет ограничений (однако производительность VirtualAlloc() уменьшится с увеличением к-ва маппингов). Есть ограничение на число маппингов (65530). Причем точное к-во использованных маппингов узнать нельзя, так как они могут быть склеены или заспличены. Существующие маппинги можно частично размапить
Объем Можно зарезервировать до 128TB виртуального адресного пространства, однако закоммитить можно столько, сколько позволит физическая память и размер свопа. Поскольку все маппинги изначально закоммичены, размер в виртуальном адресном пространстве гораздо меньше и зависит от размера RAM и swap. Однако, при наихудшем сценарии, когда каждый маппинг содержит только одну страницу лимит будет 255MB (65530 * 4k).

Выводы

  • Это не очень удобно в использовании для разработчика - нужно заботиться о многих вещах, не связанных с написанием программы;
  • Это эффективно работает работает для больших pool-ов;
  • Отсутствуют алгоритмы интеллектуального выбора pool-а или маппинга - просто выбирается следующий свободный кусок заданного размера либо аллокируется кусок с заданного адреса;
  • Поведение функционала аллокации сильно отличается в зависимости от платформы, поэтому если пишется кроссплатформенное приложение, необходимо писать много оберток для работы с этим функционалом.

Задачи аллокатора

  • нужен был удобный, простой и переносимый API, который работает одинаково на всех OS;
  • нивелирует ограничения "родных" API, предоставляемых OS;
  • не заставляет пользователя оперировать сырыми адресами, а берет эту задачу на себя и сам решает, какие адреса нужно аллокировать, пользователю же отдается уже готовый результат аллокации;
  • содержит алгоритмы, позволяющие наиболее эффективно решить задачу аллокации, то есть распределить память из pool-а по большому количеству сравнительно небольших объектов;
  • использует средства OS для аллокации.

Работа с аллокатором со стороны приложения. Ручная и автоматическая аллокация памяти

Языки с ручной аллокацией - C, C++, Objective C, Delphi

  • C - malloc, realloc, free
  • С++ - new, delete
In [1]:
>xeus-cling-cpp14
#include <iostream>
// C
// Allocates block of size 'size'
// Returns: ptr to allocated block if OK, NULL on error
void *malloc(size_t size);

// Reallocates the given area of memory.
// It must be previously allocated by malloc(), calloc() or realloc() 
// and not yet freed with a call to free or realloc. Otherwise, the results are undefined.
void *realloc( void *ptr, size_t new_size );

// Frees block pointed to by 'ptr'
// If ptr is a null pointer, the function does nothing.
// The behavior is undefined if the value of ptr does not equal a value 
// returned earlier by malloc(), calloc(), realloc(), or aligned_alloc() (since C11).
void free(void *ptr);

// example
typedef struct {
    int member;
} data_t;

data_t* ptr = (data_t*)malloc(sizeof(data_t));
ptr->member = 12345;
std::cout << ptr << "\n";
free(ptr);

0x7f8308850cc0
In [ ]:
// C++
#include <new>
void* operator new  ( std::size_t count );
void* operator new[]( std::size_t count );

void* T::operator new  ( std::size_t count );
void* T::operator new[]( std::size_t count );

void operator delete  ( void* ptr );
void operator delete[]( void* ptr );

void T::operator delete  ( void* ptr );
void T::operator delete[]( void* ptr );

// examples
int* ptr = new int[10];
ptr[2] = 1000;
....
delete[] ptr;

class Class {
public:
    int member;
};

Class* obj = new Class;
obj->member = 12345;
delete obj;
In [ ]:
#include <cstdio>
#include <cstdlib>
// переопределение new и delete
void* operator new(std::size_t sz) {
    std::printf("global op new called, size = %zu\n",sz);
    return std::malloc(sz);
}
void operator delete(void* ptr) noexcept
{
    std::puts("global op delete called");
    std::free(ptr);
}
int main() {
     int* p1 = new int;
     delete p1;
 
     int* p2 = new int[10]; // вызов переопределенного new
     delete[] p2;
}

Операторы new и delete могут быть как глобальными, так и у классов, что позволяет использовать специфические аллокаторы для выделения памяти под объекты именно этих классов (оптимизированные для них).

In [2]:
>xeus-cling-cpp14
#include <iostream>
// class-specific allocation functions
struct X {
    static void* operator new(std::size_t sz)
    {
        std::cout << "custom new for size " << sz << '\n';
        return ::operator new(sz);
    }
    static void* operator new[](std::size_t sz)
    {
        std::cout << "custom new for size " << sz << '\n';
        return ::operator new(sz);
    }
};

X* p1 = new X;
delete p1;
X* p2 = new X[10];
delete[] p2;

custom new for size 1
custom new for size 10

Размещающий new

Размещает объект на выделенной извне области памяти Для чего используется:

  • можно разместить сразу несколько объектов на одной области памяти, выделенной аллокатором;
  • отсутствует фрагментация;

Недостаток:

  • надо явно вызывать деструктор класса, иначе он не вызовется.
In [3]:
>xeus-cling-cpp14
size_t size = 10000;
char* buffer = new char[size];
std::cout << "Buffer: [" << static_cast<const void *>(buffer) << "]\n";

struct MyClass {
    int data[100];
    MyClass() {std::cout << "constructed [" << this << "]\n";}
    ~MyClass() {std::cout << "destructed [" << this << "]\n";}
};

MyClass* object1 = new (buffer) MyClass; // вызывает только конструктор, деструктор надо вызвать явно
MyClass* object2 = new (buffer + sizeof(MyClass)) MyClass;

object1->~MyClass();
object2->~MyClass();

delete[] buffer;

Buffer: [0x7f830dab2800]
constructed [0x7f830dab2800]
constructed [0x7f830dab2990]
destructed [0x7f830dab2800]
destructed [0x7f830dab2990]

Кастомный аллокатор вместо std::allocator

По умолчанию для стандартных контейнеров используется std::allocator, который аллокирует/деаллокирует через new/delete. Если вы, например, разработчик игр, вы можете использовать свой аллокатор для конкретного типа данных. Например, в неймспейсе std вектор объявлен так:

In [ ]:
template <class T, class Allocator = std::allocator<T>> class vector;

Мы можем использовать другой аллокатор вместо Allocator, и память будет резервироваться им. Например,

In [ ]:
#include <iostream>
#include <vector>

void *mymalloc(size_t size) {
    return malloc(size); // can be custom
}

void myfree(void *ptr) {
    free(p); // can be custom
}

template<typename T>
struct MyAllocatorType
{
    typedef T value_type;
};

template <class T>
struct MyAllocator {
    MyAllocator() = default;

    pointer allocate(size_type n, const void* /*hint*/ = 0) {
        return mymalloc(n * sizeof(T));
    }
    void deallocate(pointer p, size_type /*n*/) {
        myfree(p);
    }
};

using MyVector = std::vector<int, MyAllocator<int>>;
MyVector vec;
vec.push_back(1); // память аллокируется через mymalloc

Проблемы ручной аллокации памяти:

  • сделали malloc/new и не сделали free/delete. Получаем висящий указатель (dengling pointer) и утечку памяти. Все время уменьшается доступная память, но при завершении процесса OS автоматически деаллоцирует память, занятую процессом.
  • удаление одного и того же указателя более 1 раза (heap corruption). UB.
  • удаление указателя, который мы не аллокировали (violation of memory protection). UB.
  • использование памяти после удаления. UB.

Защита от проблем на уровне приложения:

Не работаем с сырыми указателями на память:

  • RAII. Делаем обертку над классом, в конструкторе аллокируем, в деструкторе освобождаем память;
  • std::unique_ptr, std::shared_ptr, std::weak_ptr.
  • COM (QueryInterface, AddRef, Release).
In [ ]:
#include <iostream>
// RAII - в конструкторе аллокируем память, в деструкторе освобождаем, не лучший вариант, но основа для unique_ptr
// обычно RAII используют для гарантированного закрытия файлов, освобождения дескрипторов и проч.
struct Object {
    Object(int init_member) 
        : member(init_member) {
    }
    int member;
};

template <typename T>
class RAIIWrapper{
public:
    template<typename... Args>
    RAIIWrapper(Args&&... args) 
       : m_object(new T(std::forward<Args>(args)...)) {
    }
    
    ~RAIIWrapper(){
        delete m_object;
    }

    T* operator -> (){
        return m_object;
    }

private:
    T *m_object;
};

// использование:
{
    RAIIWrapper<Object> object(1);
    object->member = 2;
    std::cout << object->member << std::endl;
    // object удаляется перед {
}
In [4]:
>xeus-cling-cpp14
#include <memory>

struct Object {
    Object(int init_member) 
        : member(init_member) {
    }
    int member;
};

// Примеры std::unique_ptr, std::shared_ptr, std::weak_ptr
// unique_ptr - у объекта один хозяин, владение может быть передано другому хозяину
{
    auto object = std::make_unique<Object>(1);
    object->member = 1;
    // object is destroyed before {
}

// shared_ptr - у объекта может быть много владельцев, владение копируется вместе с объектом
{
    auto object = std::make_shared<Object>(1);
    auto objectCopy = object;

    // objectCopy is destroyed
    // object is destroyed
}
    
// weak_ptr
{
    auto object = std::make_shared<Object>(1);
    // get pointer to data without taking ownership
    std::weak_ptr<Object> weak1 = object;
    // object is destroyed, we create another instance of Object with member '2'
    object = std::make_shared<Object>(2);

    // weak1 is expired!
    if (auto tmp = weak1.lock())
        std::cout << tmp->member << '\n';
    else
        std::cout << "weak is expired\n";
    
    std::weak_ptr<Object> weak2 = object;
    // weak2 points to new object (2)
    if (auto tmp = weak2.lock())
        std::cout << tmp->member << '\n';
    else
        std::cout << "weak2 is expired\n";    
}

weak is expired
2

Языки с автоматической аллокацией - Python, Java, C#, Visual Basic, Ruby, Perl, JavaScript, PHP и т.д.

Содержат средства для автоматической аллокации памяти и зачистки аллокированной памяти после того, как работа с объектом закончена. Новые появляющиеся языки обычно используют сборку мусора, потому что это удобно.

Python

Python использует счетчик ссылок для управления памятью

При выходе из scope (конца функции либо уничтожения класса, либо конца py-файла) объект уничтожается. Ссылки на объект хранятся в специальных системных словарях, которые можно получить ф-циями locals(), globals()). Для каждого объекта имеется счетчик ссылок (дополнительный оверхед). Существует механизм слабых ссылок для слежения за "сильными" ссылками и борьбы с reference cycles.

In [3]:
# Python
class Object(object):
    def __new__(cls):
        print('__new__')
        obj = super(Object, cls).__new__(cls)
            obj2 = Object()
        print(obj)
        return obj

    def __del__(self):
        print('__del__')

    def __init__(self):
        print('__init__')
        self.member = 12345

def test():
    obj = Object()
    obj.member = 1000
    
test()

__new__
<__main__.Object object at 0x108a605f8>
__init__
__del__
In [4]:
import gc

# Enable automatic garbage collection.
gc.enable()

# Disable automatic garbage collection.
gc.disable()

# Returns true if automatic collection is enabled.
gc.isenabled()

# With no arguments, run a full collection. The number of unreachable objects found is returned.
gc.collect(generation=2)
Out[4]:
60

Weak references (слабые ссылки) в Python-е

Работают аналогично std::weak_ptr в С++: слабая ссылка на объект это ссылка, которая не охраняет его от garbage collector: когда остались только слабые ссылки на объект, garbage collection уничтожает объект и память под ним переиспользуется. Основная роль слабых ссылок - реализовывать кэши объектов когда не нужно его поддерживать "живым" только из-за того, что он в кэше. Если используется где-то еще, то он живой, если только в кэше - то удаляется.

In [5]:
import weakref

def checkRef(ref):
    obj = ref()   # получает объект из слабой ссылки
    if obj is None:
        # referent has been garbage collected
        print ("Object has been deallocated.")
    else:
        print ("Object is still alive!")

obj = Object()
ref = weakref.ref(obj)
checkRef(ref)
del obj
checkRef(ref)

__new__
<__main__.Object object at 0x108a542b0>
__init__
Object is still alive!
__del__
Object has been deallocated.
In [6]:
# Кэш id->объект с использованием слабых ссылок
import weakref

_id2obj_dict = weakref.WeakValueDictionary()
def remember(obj):
    oid = id(obj)
    _id2obj_dict[oid] = obj
    return oid

def id2obj(oid):
    return _id2obj_dict[oid]

obj = Object()
obj_id = remember(obj)
print ("obj=", obj_id)
del obj
try:
    print ("obj=", id2obj(obj_id))
except KeyError:
    print ("No object", obj_id)

__new__
<__main__.Object object at 0x108a607f0>
__init__
obj= 4440066032
__del__
No object 4440066032

Java

В Java в отличие от Python не применяется garbage collecting на основе подсчета ссылок. Объект уничтожается, когда на него перестают ссылаться другие объекты. Рассмотрим garbage collector для Java позже. Обычные ссылки на объекты в Java - это так называемые "сильные" ссылки (StrongRef). Еще есть:

  • SoftRef ("мягкие" ссылки): если на объект нет сильной ссылки, но есть мягкая ссылка, то garbage collector освобождает память под этим объектом только когда ему это нужно (может и не освободить).
  • WeakRef ("слабые" ссылки, работают аналогично слабым ссылкам в C++ и Python - освобождает память, если есть слабые ссылки, но нет сильных, при очередном проходе GC);
  • PhantomRef ("фантомные ссылки"). Могут использоваться в ситуациях, когда использование финализации finalize() нецелесообразно. Это специальная ссылка, которая говорит, что объект уже финализирован, и garbage collector готов забрать его память. Получить через PhantomRef сам объект, на который она ссылается, нельзя.
In [1]:
>java
import java.lang.ref.PhantomReference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;

class Object {
    int value;
    
    public Object(int value) {
        this.value = value;
    }
}

{
    // Strong Ref
    Object object = new Object(1);
    System.out.println("Reference " + object);
}

{
    // Soft Ref
    SoftReference<Object> softRef = new SoftReference<Object>(new Object(1));
    System.out.println("Soft reference " + softRef.get());
}

{
    // Weak Ref
    int counter = 0;
    WeakReference<Object> weakRef = new WeakReference<Object>(new Object(1));
    System.out.println("Weak reference " + weakRef.get());
    while (weakRef.get() != null)
    {
        counter++;
        System.gc();
        System.out.println("Weak reference after " + counter + " loops: " + weakRef.get());
    }
}
{
    // Phantom Ref
    final ReferenceQueue queue = new ReferenceQueue();
    PhantomReference<Object> ref = new PhantomReference<Object>(new Object(1), queue);
    System.gc();
    queue.remove();
    System.out.println("Phantom reference deleted");
}

Reference REPL.$JShell$22$Object@213f20d3
Soft reference REPL.$JShell$22$Object@553e35db
Weak reference REPL.$JShell$22$Object@73caf302
Weak reference after 1 loops: null
Phantom reference deleted

C/C++

Вопрос к аудитории: есть ли автоматическая аллокация/деаллокация в C и C++?

Аллокация объектов на стеке

Screenshot%202019-03-16%20at%2007.47.34.png

In [5]:
>xeus-cling-cpp14
// С/С++

int y;   // мусор
char *str; // мусор

y = 4;   // уже не мусор
std::cout << "stack memory: " << y << "\n";

str = (char*)malloc(100*sizeof(char)); // присвоили указатель на выделенную в heap-е память, в самой памяти мусор 
str[0] = 'm';                   // 0-й элемент <= m
std::cout << "heap memory: " << str[0] << "\n"; 
free(str);                      // освобождаем память в heap-е
                                // стек освобожается сам, при выходе из main возвращается в исходное состояние

stack memory: 4
heap memory: m
In [1]:
>Java
// Работа со стеком в Java
class Class {
    public int member;
    Class() {
        this.member = 1000;        // this.member лежит в классе, но сама 1000 - в heap-е
    }
}
{
    Class obj = new Class();       // создаем новый экземпляр класса Class в heap-е, но obj лежит на стеке
    obj.member = 12345;
} // на выходе из блока member и obj уничтожаются

Как работает динамическая аллокация памяти

Malloc.png

Почему известная структура данных также называется heap? Что между ними общего? Возможно, это один и тот же heap?

  • проходили на занятии по heap-ам (она же "пирамида"). Это полное бинарное дерево, которое однозначно отображается в плоскую структуру данных (которая размещается в массиве). Значение в узле-родителе >= значений в детях. Каждый более верхний уровень пирамиды > следующего
  • у нас массив блоков. Каждый блок помечен флагом "свободен/занят". Есть ли что-то общее между тем heap-ом и нашим heap-ом? Найдем ответ на этот вопрос позже.

Как работает Heap Manager?

  • Изначально массив блоков пустой. Вызывается alloc, он ищет свободный блок, который подходит по размеру.
  • Предположим, такой блок найден. Он помечается как зарезервированный. Пользователю возвращается указатель на начало этого блока.
  • Если такого блока нет, возвращаем пользователю NULL.
  • После того, как пользователь поработал с блоком, он возвращает его обратно посредством вызова free(). Блок снова помечается как свободный.

Алгоритмы для Heap Manager

Карта памяти MemoryMap.png

  • Доказано, что не существует алгоритма, гарантирующего эффективное использование памяти при аллокации. Для любого алгоритма аллокации есть вероятность, что некоторое приложение будет аллокировать/деаллокировать блоки таким образом, что это приведет к серьезной фрагментации
  • Как вычислить фрагментацию? Условная формула наихудшего случая фрагментации для хорошего аллокатора: F=Mlog2n, где M - размер потока данных в аллокатор, n=(Nmax/Nmin) - отношение минимального размера блока к максимальному.
  • Задача алгоритма - оптимально выбрать место из свободного резерва, куда поместить блок, который пользователь собирается зааллокировать;
  • При необходимости - запросить увеличение места под heap у операционной системы;
  • Важно найти закономерности во входном потоке данных, если мы будем оперировать похожими размерами, задача упростится;
  • Можно делить и склеивать свободные блоки для нахождения подходящего по размеру;

  • Надо выбрать стратегию аллокации. Пример стратегий:

    • кладите блоки туда, где они в дальнейшем не вызовут фрагментации (нереалистично)
    • не позволяйте маленьким долгоживущим объектам не давать вам освобождать большую сплошную область памяти
    • если вы вынуждены потенциально потерять то, что осталось от расщепления блока, минимизируйте потерянную часть
    • всегда используйте блок минимального размера, больший или равный запрошенному размеру, чтобы выполнить запрос (стратегия best fit)

  • Нужно каким-то образом хранить список свободных блоков. Будем его хранить в свободной области в виде некоей структуры данных (адрес + размер свободного блока). Это может быть связанный список, сортированное дерево либо другая структура данных;

  • Для нахождения подходящего блока будем хранить в начале каждой области ее размер и указатель на следующую свободную область. Свободные блоки можно связывать в порядке увеличения/уменьшения размера, либо адреса либо в произвольном порядке.

Стратегия должна быть уточнена для практического применения, например, среди подходящих выбирайте блок с минимальным адресом.

Фрагментация

External_Fragmentation.svg.png

Фрагментация - это неспособность аллокатора переиспользовать свободную память. "Дырки", оставшиеся от деаллокации маленьких блоков, нельзя использовать в дальнейшем для аллокации блоков большего размера. Невозможность аллокатора переиспользовать память связана не только с размером и числом "дырок", но и с будущим поведением программы и самого аллокатора. Например, предположим у нас есть 100 свободных блоков размера 10 и 200 свободных блоков размера 20. Память сильно фрагментирована? Это зависит от будущих реквестов. Если будущие реквесты все будут на размер 10, все будет ок, аллокаторы будут использовать блоки на 10 и сплитить блоки на 20. Если же будут реквесты на 30,􏰂 то это проблема. Если придет 100 реквестов на 10 и 200 на 20, то все зависит от порядка, в котором придут запросы и от решений аллокатора по каждому запросу, куда поместить эти блоки. В данном случае решение best fit работает хорошо.

Фрагментация:

  • внутренняя
  • внешняя

Внешняя фрагментация получается, когда есть свободные блоки, доступные для аллокации, но их нельзя использовать для хранения объектов запрошенных размеров. Внутренняя фрагментация - когда аллокируется подходящий по размеру, но слишком большой блок. При этом остаток просто расходуется впустую, вызывая фрагментацию. Чтобы противостоять внутренней фрагментации, аллокаторы делят блок на несколько частей - после аллокирования части остальное считается новым пустым блоком. Также можно сливать соседние пустые блоки в блоки большего размера.

Фрагментация вызывается "изолированными смертями": соседний блок "умер"->появилась фрагментация. Если блоки "умирают" вместе - фрагментации не происходит. Аллокатор, который может "предсказать", какие объекты "умрут" вместе, может поместить их рядом. Поведение программы влияет на будущую фрагментацию.

Какие будут идеи у аудитории как можно решить задачу наиболее эффективно?

  • для уменьшения фрагментации нельзя перемещать заалокированный участок памяти, поскольку его уже отдали пользователю;
  • идеальный вариант - найти наименьший свободный блок, подходящий по размеру, но это требует сканирования всего массива блоков. Другая крайность - вернуть первый попавшийся подходящий. Таким образом, балансируем между оптимальной производительностью и эффективностью распределения памяти. И то, и то одновременно недостижимо (best fit vs first fit).

Поведение программы

Важно понять, каково поведении реальных программ при аллокации памяти и подобрать соответствующую стратегию аллокатора.

  • программа может постоянно, но медленно аллокировать новые объекты, например, для записи в лог;
  • программа может аллокировать сразу много объектов (конструируя большие структуры данных), а затем недолго их использовать и удалять;
  • программа может аллокировать много объектов и использовать их очень долго.
  • как оказывается, другие паттерны поведения не очень часто встречаются. Паттерны могут сочетаться между собой в разных комбинациях в реальных программах. Особенно важно отсутствие фрагментации при пиковой нагрузке (сценарий 2). Когда памяти занято мало, фрагментация не так влияет. Объекты, которые аллокируются почти одновременно, должны располагаться в соседних блоках. Если они и освобождаются почти одновременно то фрагментации не будет.

Компилятор C компилирует собственный исходник (аллокирует сразу много, но не надолго) Alloc1.png

Расчетная математическая программа (представляет сложное выражение в виде линейной комбинации полиномов) - постоянно и медленно аллокирует объекты Alloc2.png

Скрипт на perl-е, обрабатывающий строки (аллокирует сразу много и надолго) Alloc3.png

Выводы

  • различные программы могут демонстрировать разное поведение при аллокации.
  • поведение программ меняется с течением времени, оно не постоянно;
  • важно пиковое потребление памяти и фрагментация в это время;
  • фрагментация вызывается вариативным поведением программы, особенно когда аллокируется много объектов разных размеров;

Алгоритмы:

  • Sequential fits
  • Segregated Free Lists
  • Buddy alloc
  • Indexed fits
  • Bitmapped fits
  • Slab alloc

Sequential fits

  • разновидности - first fit, next fit, best fit, worst fit;
  • поддерживаем один линейный список всех свободных блоков (двусвязный или кольцевой список);
  • существуют LIFO и FIFO варианты, когда освобождающиеся блоки помещаются в начало/конец очереди, если используется FIFO-вариант, освобождающиеся блоки долго не будут использоваться вновьe;
  • при большом количестве блоков можно использовать деревья поиска (поиск log(N) вместо N);
  • можно сортировать по размеру либо по адресу;
  • поддерживаем boundary tags длия простого слияния свободных блоков;

Best fit

Последовательно перебирает список свободных блоков, пока не найдет блок минимального размера, удовлетворяющий запросу; Цель - минимизировать размер неиспользуемого места, убедившись, что фрагменты имеют минимальный допустимый размер. Недостатки - даже при таком подходе мы не можем гарантировать отсутствие фрагментации, плохой worst-case перформанс.

First fit

Последовательно перебираем список свободных блоков, пока не найдет первый подходящий блок. Если блок имеет больший размер, чем нужно, он делится на 2 и остаток помещается в список свободных блоков.

Next fit

Оптимизация first fit - "roving pointer" - бродячий указатель. Запоминается позиция, на которой последний поиск был успешным и следующий поиск начинается с неё.

Worst fit

Используется всегда свободный блок наибольшего размера в надежде избежать образования маленьких неиспользуемых фрагментов, поддерживая остаток наибольшим􏰄.

Segregated free lists

Это массив списков свободных блоков, сгруппированных по размеру. Когда нужен блок определенного размера, выбираем его из соответствующего списка. Вариант: использовать классы размеров, например, группировать по степеням двойки: 2 слова, 2^2, 2^3 и т.д. При запросе округлять вверх. Когда поступает запрос от пользователя на размер ищем соответствующий класс. Если список класса пуст, запрашиваем 1 или 2 страницы у системы, разбиваем на блоки по размеру и добавляем в список блоков.

Достоинства:

  • быстрый алгоритм.

Недостатки:

  • возможна очень серьезная фрагментация из-за фиксированных размеров блоков;
  • неэффективно использует память - если программа запрашивает один и тот же размер, остальные размеры не используются.

Buddy systems

Это оптимизированный Segregated free lists. Возможен сплит/слияние блоков, но только со своими buddies (приятелями). 64K c 64K и т.д. Простая схема - весь heap делится на 2 большие части. Каждая из частей делится еще на 2. Это позволяет привязать аллокацию к конкретному месту. В общем массиве списков есть список для каждого размера. Приближение к best-fit. Buddy.png

Indexed fits

Это sequential fits, которые индексируются специальным образом. Например, алгоритм best fit на самобалансирующемся дереве, сортированное по размеру блока. Иногда используется декартово дерево, сортированное по размеру и адресу - Stephenson􏰒's 􏰅Fast Fits􏰆 allocator.

Bitmapped fits

Используется bitmap (1-бит вектор) для обозначения пустых областей в heap. 1 бит - 1 слово. Используется чаще не в аллокаторах, а в mark-sweep garbage collector-ах (рассматриваем далее).

  • недостаток - медленный алгоритм;
  • достоинство - поиск по точному адресу.

Slab alloc

Аллокатор подстраивается под программу. Заточен под хранение объектов одного типа или размера. С++ имеет возможность создавать отдельный аллокатор для каждого класса. Аллокатор содержит список свободных блоков для данного типа и выдает их при необходимости.

Применение Slab alloc

  • UNIX-совместимые системы (в ядре Linux, FreeBSD, Solaris);
  • perl5 использует slab allocator для внутреннего менеджмента памяти;
  • memcached для менеджмента памяти

Сборщик мусора (Garbage collector)

Рассмотрим алгоритмы GC на примере Java. Аллокируем через heap manager память вручную, но освобождается она автоматически.

Стратегии сборки мусора:

  • счетчик ссылок;
  • использование транзитивное замыкание всех ссылок (компонентов связности) в графе объектов;
  • вообще не удалять, а когда память кончится, просто прибить процесс (иногда имеет смысл, во избежание фрагментации);
  • запуск garbage collector - ручной или автоматический;

Подсчет ссылок

Достоинства

  • не требует "остановки" ("stop-the-world") процесса;
  • несложный в реализации.

Недостатки:

  • не удастся "поймать" кольцевые ссылки;
  • подсчет ссылок в многопоточной среде

Компоненты связности

Задача поиска компонент связности в графе

Дан неориентированный граф G с n вершинами и m рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.

В нашем случае задача упрощается потому что граф - ориентированный и есть фиксированные root-ы.

Как узнать, что именно нужно освобождать? Надо найти объекты, на которые не ссылаются никакие другие объекты и освободить память, которую они занимают, причем как можно более эффективно. Heap - корневой объект + набор объектов. Gc.png

Каждый объект имеет адрес, размер и набор ссылок на другие объекты (например, их адреса). Никакие два объекта не могут перекрываться. Heap можно представить как направленный граф с вершинами o=(a,s) (адрес, размер), ребра - связи между объектами. Надо найти компоненты связности графа. В данном случае o3, o4 и o5 недостижимы из root-а и должны быть удалены. Нужен набор корневых объектов - это статические переменные и локальные переменные.

Недостаток

  • требуют "остановки мира", потому что граф не должен меняться во время обхода;

Алгоритм Copying Garbage Collection

  • начинает с корней объектов, проходится по всем достижимым объектам, копируя их из одной половины памяти в другую (из "старой" в "новую").
  • при копировании делаем compaction памяти, то есть получается сплошной блок и дефрагментация исчезает.
  • после копирования и компакшна у нас получается копия достижимых данных в новой области памяти.
  • когда в следующий раз будем делать garbage collection, роли новой и старой памяти меняются местами. Копируем из "новой" в "старую" и т.д.
  • для прохода по объектам используем BFS/очередь или DFS/стек
root O1 O2 O3 O4 O5 - - - - - -
- - - - - - root O1 O2 - - -

Алгоритм Mark-Sweep

В алгоритме mark-sweep для сбора мусора весь процессинг останавливается. Каждый объект имеет “mark-bit”, который используется для обозначения, посещен ли объект во время сборки мусора.

In [ ]:
mark-sweep:
    mark(root)
    sweep()

mark(o):
    if o.mark-bit == 0:
        o.mark-bit = 1
        for p in o.references():
            mark(p)
        
sweep():
    o = 0
    while o < N
        if o.mark-bit == 1:
            o.mark-bit = 0
        else:
            free(o)
            
        o = o + size(o)

Вопрос: какова алгоритмическая сложность алгоритма mark-sweep?

Достоинства:

  • освобождает всю неиспользуемую память.

Недостатки:

  • требует полной остановки процессинга для своей работы;
  • есть оверхед в 1 бит (mark-bit), но он может быть переиспользован в то время, когда алгоритм не работает;
  • освобождаемая память подвержена фрагментации.

Алгоритм Mark-Sweep-Compact

  • построен на базе mark-sweep;
  • после sweep перемещает живую память в другую область для дефрагментации.

Домашнее задание - опционально (не проверяется, решения публикуем в слак)

Вариант 1 (С/С++)- сделать свой менеджер памяти (heap manager)

Можно сделать реализацию best fit, first fit или взять любую другую

Цели:

  • лучше понять, как наиболее эффективно распределять память для хранения данных;
  • поработать с алгоритмами распределения памяти.

Задача:

  • сделать свой heap manager, реализовав функции malloc и free (+new, delete, new[] и delete[]).
  • можно использовать любой известный алгоритм либо придумать свой.

Требования к реализации:

  • запросы на аллокацию могут приходить в любой последовательности (выделили 1 блок, потом еще, потом освободили первый и т.д.). Менеджер памяти должен правильно обрабатывать эти ситуации;
  • выделяемые участки памяти должны быть выровнены по границе объекта максимального размера, который может отдавать менеджер (нап., 8 байт для 64-битных систем);
  • нельзя модифицировать или перемещать блоки памяти, которые уже были выделены пользователю, пока он не освободит их;
  • в случае удаления неаллокированного блока поведение менеджера памяти не определено;
  • постарайтесь спроектировать heap manager по возможности наиболее эффективно, чтобы использовать память эффективно, одновременно уменьшив фрагментацию памяти настолько, насколько это возможно;
  • выделение памяти для работы самого менеджера должно производиться на этом же самом heap;
  • стоит уделить время производительности менеджера памяти, чтобы он отвечал на запросы так быстро, как только возможно;
  • должны присутствовать тесты, показывающие правильность работы heap manager;
  • (опционально) написать тесты производительности, меряющие производительность вашего менеджера памяти и сравнивающие его со стандартной реализацией менеджера памяти в вашей реализации языка C.

Вариант 2 (Python) - сделать свой сборщик мусора (garbage collector) с учётом ссылок на объект

Цели:

  • лучше понять, как работает сборщик мусора на базе алгоритмов Copying Garbage Collector/Mark-Sweep.

Задача:

  • сделать свой garbage collector на Python, реализовав функции учета ссылок на объект и "условное" освобождение объекта.
  • можно использовать любой алгоритм из числа Copying Garbage Collector/Mark-Sweep.
  • написать тесты, которые показывают, что алгоритм работает

Вариант 3 (Java) - сделать свой сборщик мусора (garbage collector) с подсчетом ссылок

Цели:

  • лучше понять, как работает сборщик мусора на базе reference counter.

Задача:

  • сделать свой garbage collector на Java, реализовав функции подсчета внешних ссылок на объект и "условное" освобождение объекта.
  • можно использовать любой известный алгоритм, связанный с подсчётом ссылок на объект либо придумать свой.
  • написать тесты, которые показывают, что алгоритм работает

Заполните опросник в конце занятия: https://docs.google.com/forms/d/e/1FAIpQLSdiatBup4OlDyxR7laLuZl_qKtlJE228W5VrsHnw5GmPf7ZPQ/viewform

Полезные ссылки и литература

Архитектура компьютерных систем

Аллокаторы

Garbage Collection